iT邦幫忙

2024 iThome 鐵人賽

DAY 17
0

先上今天拍的月亮,中秋快樂~~~
https://ithelp.ithome.com.tw/upload/images/20240917/20168787ywtjJLcRjq.jpg

題目

884. Uncommon Words from Two Sentences
難度: 用c++的話簡單

題意

給定兩字串s1s2。字串可被空白字元切成單字。
求一字串陣列,包含所有不平常單字
不平常單字為在其中一個字串出現一次,另一個字串沒有出現的單字。

思路

查詢有無出現、查詢出現幾次的題目類型,都優先用哈希表解。
先用兩個哈希表分別記錄兩個字串中,個別單字的出現次數;再遍歷兩哈希表的單字,檢查此單字在另一個哈希表出現的次數。

實作

可以使用istringstream將字串轉換成字串流,可以很方便的分割空白字元。
我邊查語法邊寫的,用C大概會刻到吐。

typedef std::__cxx11::basic_istringstream std::istringstream
Class for @c char input memory streams.

class Solution
{
public:
    vector<string> uncommonFromSentences(string s1, string s2)
    {
        istringstream iss1(s1);
        istringstream iss2(s2);
        // Hash map for s1, string -> count
        unordered_map<string, int> um1;
        // Hash map for s2, string -> count
        unordered_map<string, int> um2;

        // Split string in sentence and count number
        string str;
        while (iss1 >> str)
            um1[str]++;
        while (iss2 >> str)
            um2[str]++;

        // Find uncommon words
        vector<string> res;
        for (auto word : um1)
            if (word.second == 1 && um2.find(word.first) == um2.end())
                res.push_back(word.first);
        for (auto word : um2)
            if (word.second == 1 && um1.find(word.first) == um1.end())
                res.push_back(word.first);

        return res;
    }
};

分析

s1長度為N1,s2長度為N2
時間複雜度: O(N1 + N2) = O(max(N1, N2)),每個單字建表、查表都最多各一次。
空間複雜度: O(N1 + N2),哈希表所需的空間。

結果

Time Submitted Status Runtime Memory Language
09/17/2024 22:17 Accepted 5 ms 9.2 MB cpp

Accepted
55/55 cases passed (5 ms)
Your runtime beats 15.91 % of cpp submissions
Your memory usage beats 22.25 % of cpp submissions (9.2 MB)


上一篇
[9/16] 最短時間差
下一篇
[9/18] 使整數串接起來最大
系列文
菜就多練,不會就多刷31
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言